#include <bits/stdc++.h>
using namespace std;

// 归并排序，填函数练习风格
// 测试链接 : https://leetcode.cn/problems/sort-an-array/

class Solution 
{
private:
    static const int MAXN = 50001;
    int help[MAXN]; 

    void merge(vector<int>& nums, int l, int m, int r)
    {
        int i = l, a = l, b = m + 1;
        while(a <= m && b <= r)
        {
            help[i++] = nums[a] <= nums[b] ? nums[a++] : nums[b++];
        }

        while(a <= m) help[i++] = nums[a++];
        while(b <= r) help[i++] = nums[b++];
        for(i = l; i <= r; ++i) nums[i] = help[i];
    }

    void mergeSort1(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;

        int m = l + ((r - l) >> 1);
        mergeSort1(nums, l, m);
        mergeSort1(nums, m + 1, r);
        merge(nums, l, m, r);
    }

    void mergeSort2(vector<int>& nums)
    {
        int n = nums.size();
        for(int l, m, r, step = 1; step < n; step <<= 1)
        {
            l = 0;
            while(l < n)
            {
                m = l + step - 1;
                if(m + 1 >= n) break;
                r = min(l + (step << 1) - 1, n - 1);
                merge(nums, l, m, r);
                l = r + 1;
            }
        }
    }

public:
    vector<int> sortArray(vector<int>& nums) 
    {
        if(nums.size() > 1) 
        {
            // mergeSort1(nums, 0, nums.size() - 1);
            mergeSort2(nums);
        }
        return nums;
    }
};